home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 13 - 1997 (partial) / 13.04 Apr 97 / DesignPatterns / Patterns.cc next >
Encoding:
C/C++ Source or Header  |  1997-01-06  |  7.9 KB  |  395 lines  |  [TEXT/CWIE]
  1. /*
  2.  *  Design Patterns Examples
  3.  *  © 1997 John Schettino, js12@gte.com
  4.  *
  5.  */
  6.  
  7. #include "Patterns.h"
  8. #include <iostream.h>
  9.  
  10. // This example uses the IterateDirectory() function from MoreFiles 1.4.3
  11. // This Apple - supplied code is available from
  12. // ftp://ftpdev.info.apple.com/Developer_Services/Sample_Code/MoreFiles_1.4.3/
  13. #include "IterateDirectory.h" 
  14.  
  15. // -- Binary Tree Node member fns --
  16.  
  17.  
  18. ostream&
  19. operator<< (ostream& os, const TreeNodePtr& t)
  20. {
  21.     os << *t; return os;
  22. }
  23.  
  24. ostream&
  25. operator<< (ostream& os, TreeNode& t)
  26. {
  27.     os << "[" <<  t.output() << "]\n";
  28.     return os;
  29. }
  30.  
  31.  
  32. // -- DFTreeNodeIterator member fns --
  33.  
  34. DFTreeNodeIterator::DFTreeNodeIterator(BinaryTreeNode &tree)
  35. {
  36.     _origTree = _tree = &tree;
  37.     _pushLeft();
  38. }
  39.  
  40. // follow left branch pushing nodes onto stack
  41. // done for every first-time visit
  42.  
  43. void
  44. DFTreeNodeIterator::_pushLeft()
  45. {
  46.     while (_tree->leftChild())
  47.     {
  48.         _pendingNodes.push(_tree);
  49.         _tree = _tree->leftChild();
  50.     }            
  51. }
  52.  
  53. // postfix ++
  54.  
  55. TreeNodePtr
  56. DFTreeNodeIterator::operator++ (int)
  57. {
  58.     TreeNode* theNode = current();
  59.     next();
  60.     return theNode;
  61. }
  62.  
  63. TreeNodePtr
  64. DFTreeNodeIterator::current ()
  65. {
  66.     return _tree;
  67. }
  68.  
  69. // this is the  prefix ++ operator
  70. TreeNodePtr
  71. DFTreeNodeIterator::next()
  72. {
  73.     if (_tree)
  74.     {
  75.         // follow right child ptr
  76.         if (_tree->rightChild())
  77.         {
  78.             _tree = _tree->rightChild();
  79.             _pushLeft();
  80.         }
  81.         else if (_pendingNodes.size() > 0)
  82.         {    // end of a branch, pop up and return node itself
  83.             _tree = _pendingNodes.top();
  84.             _pendingNodes.pop();
  85.         }
  86.         else
  87.             _tree = 0; // all done
  88.     }
  89.     return _tree;
  90. }            
  91.  
  92. // reset the iterator to the first node
  93. void
  94. DFTreeNodeIterator::reset()
  95. {
  96.     _tree = _origTree;
  97.     _pushLeft();
  98. }
  99.  
  100. // -- BFTreeNodeIterator member fns --
  101.  
  102. BFTreeNodeIterator::BFTreeNodeIterator(BinaryTreeNode &tree)
  103. {
  104.     _origTree = _tree = &tree;
  105.     _current = IO_node;
  106. }
  107.  
  108. TreeNodePtr
  109. BFTreeNodeIterator::operator++ (int)
  110. {
  111.     TreeNode* theNode = current();
  112.     next();
  113.     return theNode;
  114. }
  115.  
  116. // this is the * operator
  117. TreeNodePtr
  118. BFTreeNodeIterator::current ()
  119. {
  120.     if (!_tree) return 0;
  121.     
  122.     switch (_current) {
  123.     case IO_node:
  124.         return _tree;
  125.     case IO_left:
  126.         return _tree->leftChild();
  127.     case IO_right:
  128.         return _tree->rightChild();
  129.     }
  130.     
  131. }
  132.  
  133. // this is the prefix ++ operator
  134. TreeNodePtr
  135. BFTreeNodeIterator::next()
  136. {
  137.     BinaryTreeNodePtr c;
  138.     switch (_current) {
  139.     case IO_node:
  140.         if (_tree->leftChild()) _current = IO_left;
  141.         else if (_tree->rightChild()) _current = IO_right;
  142.         else if (_pendingNodes.size() > 0)
  143.         {
  144.             _tree = _pendingNodes.front();
  145.             _pendingNodes.pop();
  146.             _current = _tree->leftChild() ? IO_left : IO_right;
  147.         }
  148.         else _tree = 0;        
  149.         return current();
  150.     case IO_left:
  151.         c = (BinaryTreeNodePtr) current();
  152.         if (c->leftChild() || c->rightChild()) _pendingNodes.push(c);
  153.         if (_tree->rightChild()) _current = IO_right;
  154.         else if (_pendingNodes.size() > 0)
  155.         {
  156.             _tree = _pendingNodes.front();
  157.             _pendingNodes.pop();
  158.             _current = _tree->leftChild() ? IO_left : IO_right;
  159.         }        
  160.         else _tree = 0;        
  161.         return current();
  162.     case IO_right:
  163.         c = (BinaryTreeNodePtr) current();
  164.         if (c->leftChild() || c->rightChild()) _pendingNodes.push(c);
  165.         if (_pendingNodes.size() > 0)
  166.         {
  167.             _tree = _pendingNodes.front();
  168.             _pendingNodes.pop();
  169.             _current = _tree->leftChild() ? IO_left : IO_right;
  170.         }        
  171.         else _tree = 0;        
  172.         return current();
  173.     }
  174. }        
  175.  
  176. // reset the iterator to the first node
  177. void
  178. BFTreeNodeIterator::reset()
  179. {
  180.     _tree = _origTree;
  181.     _current = IO_node;
  182. }
  183.     
  184.  
  185. // -- BinaryTreeBuilder member fns --
  186.  
  187. BinaryTreeBuilder::BinaryTreeBuilder() 
  188. {
  189.  _currentBTree = 0;
  190. }
  191.  
  192. TreeNodePtr
  193. BinaryTreeBuilder::GetTree() 
  194. {
  195.     return _currentBTree;
  196. }
  197.  
  198. void
  199. BinaryTreeBuilder::AddNode(TreeNode* theNode) 
  200. {
  201.     BinaryTreeNodePtr testNode =  (BinaryTreeNodePtr) _currentBTree;
  202.     if (!testNode) _currentBTree = theNode;
  203.     else
  204.     {
  205.         for (;;)
  206.         {
  207.             if (((BinaryTreeNodePtr)theNode)->compare(*testNode) <0)
  208.             {
  209.                 if (testNode->leftChild()) testNode = testNode->leftChild();
  210.                 else 
  211.                 {
  212.                     testNode->setLeftChild((BinaryTreeNodePtr)theNode);
  213.                     return;
  214.                 }
  215.             }
  216.             else 
  217.             {
  218.                 if (testNode->rightChild()) testNode = testNode->rightChild();
  219.                 else 
  220.                 {
  221.                     testNode->setRightChild((BinaryTreeNodePtr)theNode);
  222.                     return;
  223.                 }
  224.             }
  225.         }
  226.     }
  227. }
  228.  
  229. // -- HBTreeBuilder member fns --
  230.  
  231. HBTreeBuilder::HBTreeBuilder() 
  232. {
  233.  _currentBTree = 0;
  234. }
  235.  
  236. TreeNodePtr
  237. HBTreeBuilder::GetTree() 
  238. {
  239.     return _currentBTree;
  240. }
  241.  
  242. void
  243. HBTreeBuilder::AddNode(TreeNode* theNode) 
  244. {
  245.     BinaryTreeNodePtr testNode =  (BinaryTreeNodePtr) _currentBTree;
  246.     if (!testNode) _currentBTree = theNode;
  247.     else
  248.     {
  249.         BinaryTreeNodePtr grandparent = 0, parent = 0;
  250.         for (;;)
  251.         {
  252.             if (((BinaryTreeNodePtr)theNode)->compare(*testNode) <0)
  253.             {
  254.                 if (testNode->leftChild())
  255.                 {
  256.                     grandparent = parent;
  257.                     parent = testNode;
  258.                     testNode = testNode->leftChild();
  259.                 }
  260.                 else 
  261.                 {
  262.                     // try to ballance a tree that has a long left chain
  263.                     if (parent && grandparent &&
  264.                         !(parent->rightChild()) && !(testNode->rightChild()))
  265.                     {
  266.                         if (parent->compare(*grandparent) <0) grandparent->setLeftChild(testNode);
  267.                         else grandparent->setRightChild(testNode);
  268.                         parent->setLeftChild(0);
  269.                         testNode->setRightChild(parent);
  270.                     }
  271.                     testNode->setLeftChild((BinaryTreeNodePtr)theNode);
  272.                     return;
  273.                 }
  274.             }
  275.             else 
  276.             {
  277.                 if (testNode->rightChild())
  278.                 {
  279.                     grandparent = parent;
  280.                     parent = testNode;
  281.                     testNode = testNode->rightChild();
  282.                 }
  283.                 else 
  284.                 {
  285.                     // try to ballance a tree that has a long right chain
  286.                     if (parent && grandparent &&
  287.                         !(parent->leftChild()) && !(testNode->leftChild()))
  288.                     {
  289.                         if (parent->compare(*grandparent) <0) grandparent->setLeftChild(testNode);
  290.                         else grandparent->setRightChild(testNode);
  291.                         parent->setRightChild(0);
  292.                         testNode->setLeftChild(parent);
  293.                     }
  294.                     testNode->setRightChild((BinaryTreeNodePtr)theNode);
  295.                     return;
  296.                 }
  297.             }
  298.         }
  299.     }
  300. }
  301.  
  302.  
  303. // -- callback for IterateDirectory() --
  304. // adds name of each file as a node in the tree
  305. // tree builder passed in tbuilder variable
  306.  
  307. pascal
  308. void
  309. getName(const CInfoPBRec * const cpbPtr,
  310.                     Boolean *quitFlag,
  311.                     void *tbuilder)
  312. {
  313.     char *cstr = p2cstr(cpbPtr->hFileInfo.ioNamePtr);
  314.     ((TreeBuilder *)tbuilder)->AddNode(new BinaryTreeNode(cstr));
  315. }
  316.  
  317. // -- walk a tree using the TreeNodeIterator
  318. // use the current/next member functions
  319.  
  320. void walkTree1(TreeNodeIterator &treeNodes)
  321. {
  322.     cout << 
  323.         "* Fetching nodes via current/next operators\n";
  324.     
  325.     for ( ;treeNodes.current(); treeNodes.next())
  326.         cout << treeNodes.current();
  327. }
  328.  
  329. // -- walk a tree using the TreeNodeIterator
  330. // use the ++ operator
  331.  
  332. void walkTree2(TreeNodeIterator  &treeNodes)
  333. {
  334.     cout << "* Fetching nodes via ++ operator\n";
  335.  
  336.     while (TreeNodePtr p = treeNodes++)
  337.         cout << p;
  338.  
  339. }
  340.  
  341. // -- main program allocates two treeBuilders,
  342. // calls IterateDirectory() on a test directory to
  343. // populate the trees, and the creates several different
  344. // iterators and "walks" the trees.
  345.  
  346. void main(void)
  347. {
  348.     cout << "Building binary tree\n";
  349.  
  350.     BinaryTreeBuilder b;
  351.  
  352.     // iterate over a directory named Example Dir
  353.     // within the program's current working directory
  354.     StringPtr dir = c2pstr(":Example Dir");
  355.  
  356.     IterateDirectory(0,0,dir,2,getName, &b);
  357.     TreeNodePtr myTree = (BinaryTreeNodePtr) b.GetTree();
  358.     
  359.     cout << "The nodes, using a depth-first iterator:\n";
  360.  
  361.     DFTreeNodeIterator depthFirst(*(BinaryTreeNodePtr)myTree);
  362.     walkTree1(depthFirst);
  363.     
  364.     cout << "\nThe nodes, same iterator, alternate API:\n";
  365.  
  366.     depthFirst.reset();
  367.     walkTree2(depthFirst);
  368.         
  369.     cout << "\nThe nodes, using a bredth-first iterator:\n";
  370.  
  371.     BFTreeNodeIterator bredthFirst(*(BinaryTreeNodePtr)myTree);
  372.     walkTree2(bredthFirst);
  373.  
  374.     cout << "\nBuilding height balanced binary tree\n";
  375.  
  376.     HBTreeBuilder hb;
  377.  
  378.     IterateDirectory(0,0,dir,2, getName, &hb);
  379.     myTree = (BinaryTreeNodePtr) hb.GetTree();
  380.  
  381.     cout << "The HB nodes, using a depth-first iterator:\n";
  382.         
  383.     DFTreeNodeIterator depthFirstHB(*(BinaryTreeNodePtr)myTree);
  384.     walkTree2(depthFirstHB);
  385.  
  386.     cout << "\nThe HB nodes, using a BF iterator:\n";
  387.  
  388.     BFTreeNodeIterator bredthFirstHB(*(BinaryTreeNodePtr)myTree);
  389.     walkTree2(bredthFirstHB);
  390.     
  391.     cout << "\nDone\n";
  392. }
  393.  
  394.  
  395.